#include "temu.h"

/* We use the POSIX regex functions to process regular expressions.
 * Type 'man regex' for more information about POSIX regex functions.
 */
#include <sys/types.h>
#include <regex.h>

enum {
	NOTYPE = 256, EQ, NEQ, AND, OR, NUM, REG, REF, NEG

	/* TODO: Add more token types */

};

static struct rule {
	char *regex;
	int token_type;
} rules[] = {

	/* TODO: Add more rules.
	 * Pay attention to the precedence level of different rules.
	 */

	{"0x[0-9A-Fa-f]{1,8}", NUM},	// hex
	{"\\$[a-z0-9]{1,15}", REG},	// register
	{" +",	NOTYPE},				// spaces
	{"\\+", '+'},					// plus
	{"==", EQ},						// equal
	{"-", '-'},						// minus
	{"\\*", '*'},					// multiply
	{"/", '/'},						// divide
	{"%", '%'},						// mod
	{"!=", NEQ},					// not equal
	{"&&", AND},					// and
	{"\\|\\|", OR},					// or
	{"!", '!'},						// not
	{"\\(", '('},
	{"\\)", ')'},
	{"[0-9]{1,10}", NUM},			// dec
	

};

#define NR_REGEX (sizeof(rules) / sizeof(rules[0]) )

static regex_t re[NR_REGEX];

/* Rules are used for many times.
 * Therefore we compile them only once before any usage.
 */
void init_regex() {
	int i;
	char error_msg[128];
	int ret;

	for(i = 0; i < NR_REGEX; i ++) {
		ret = regcomp(&re[i], rules[i].regex, REG_EXTENDED);
		if(ret != 0) {
			regerror(ret, &re[i], error_msg, 128);
			Assert(ret == 0, "regex compilation failed: %s\n%s", error_msg, rules[i].regex);
		}
	}
}

typedef struct token {
	int type;
	char str[32];
} Token;

Token tokens[32];
int nr_token;

uint32_t get_reg_val(const char *s, bool *success);

static bool make_token(char *e) {
	int position = 0;
	int i;
	regmatch_t pmatch;
	
	nr_token = 0;

	while(e[position] != '\0') {
		/* Try all rules one by one. */
		for(i = 0; i < NR_REGEX; i ++) {
			if(regexec(&re[i], e + position, 1, &pmatch, 0) == 0 && pmatch.rm_so == 0) {
				char *substr_start = e + position;
				int substr_len = pmatch.rm_eo;

				// Log("match rules[%d] = \"%s\" at position %d with len %d: %.*s", i, rules[i].regex, position, substr_len, substr_len, substr_start);
				position += substr_len;

				/* TODO: Now a new token is recognized with rules[i]. Add codes
				 * to record the token in the array `tokens'. For certain types
				 * of tokens, some extra actions should be performed.
				 */

				switch(rules[i].token_type)
				{
					case NOTYPE: 
						break;
					case NUM: case REG:
						sprintf(tokens[nr_token].str, "%.*s", substr_len, substr_start);
					default:
						tokens[nr_token].type = rules[i].token_type;
						nr_token++;
				}

				break;
			}
		}

		if(i == NR_REGEX) {
			printf("no match at position %d\n%s\n%*.s^\n", position, e, position, "");
			return false;
		}
	}

	return true; 
}

bool check_parentheses(int p, int q){
	if(tokens[p].type != '(' || tokens[q].type != ')') return false;
	else
	{
		int num_check = 0;
		int temp;
		for(temp = p; temp < q - 1 ; temp++)
		{	
			if(tokens[temp].type == '(') num_check++;
			if(tokens[temp].type == ')') num_check--;
			if(num_check < 1) return false;
		}
		return true;
	}
}

int find_dominant_op(int p, int q){
	int check;
	int op = p;
	int i;
	for(check = p; check < q; check++)
	{
		switch(tokens[check].type)
		{
		case REG: case NUM: 
			break;

		case '(':
			i = check;
			while(!check_parentheses(i,check)) check++;
			continue;
			break;

		case OR: case AND: case EQ: case NEQ:
			op = check;
			break;

		case '+': case '-':
			if(tokens[op].type != EQ && tokens[op].type != OR && tokens[op].type != AND && tokens[op].type != NEQ)
				op = check;
			break;

		case '*': case '/':
			if(tokens[op].type == '*' || tokens[op].type == '/' || tokens[op].type == NEG || op == p)
				op = check;
			break;
		default:
			continue;
		}
	}
	return op;
}

uint32_t eval(int p, int q, bool *success) {
	if(p > q)
	{
		// 表达式非法
		*success = false;
		return 0;
	}
	else if(p == q)
	{
		uint32_t val;
		switch(tokens[p].type)
		{
			case REG: 
				val = get_reg_val(tokens[p].str, success);
				if(!*success) return 0;
				break;

			case NUM: 
				val = strtol(tokens[p].str, NULL, 0); 
				break;

			default: 
				assert(0);
		}

		*success = true;
		return val;
	}
	else if(tokens[p].type == '(' && tokens[q].type == ')') return eval(p + 1, q - 1, success);
	else
	{
		int dominated_op = find_dominant_op(p, q);
		int op_type = tokens[dominated_op].type;

		if(op_type == '!' || op_type == NEG || op_type == REF)
		{
			// 单目运算符
			uint32_t val = eval(dominated_op + 1, q, success);
			if(!*success) return 0;

			switch(op_type)
			{
				case '!': 
					return !val;
				case NEG: 
					return -val;
				case REF: 
					return mem_read(val, 4);
				default: 
					assert(0);
			}
		}

		// 二元运算

		uint32_t val1 = eval(p, dominated_op - 1, success);
		if(!*success) return 0;
		uint32_t val2 = eval(dominated_op + 1, q, success);
		if(!*success) return 0;

		switch(op_type)
		{
			case '+': 
				return val1 + val2;
			case '-': 
				return val1 - val2;
			case '*': 
				return val1 * val2;
			case '/': 
				return val1 / val2;
			case '%': 
				return val1 % val2;
			case EQ: 
				return val1 == val2;
			case NEQ: 
				return val1 != val2;
			case AND: 
				return val1 && val2;
			case OR: 
				return val1 || val2;
			default: 
				assert(0);
		}
	}
}

uint32_t expr(char *e, bool *success) {
	if(!make_token(e)) {
		*success = false;
		return 0;
	}

	/* TODO: Insert codes to evaluate the expression. */
	// panic("please implement me");

	int i, prev_type;
	for(i = 0; i < nr_token; i ++) 
	{
		if(tokens[i].type == '-') 
		{
			if(i == 0) 
			{
				tokens[i].type = NEG;
				continue;
			}

			prev_type = tokens[i - 1].type;
			if(!(prev_type == ')' || prev_type == NUM || prev_type == REG))
				tokens[i].type = NEG;
		}

		else if(tokens[i].type == '*') 
		{
			if(i == 0) 
			{
				tokens[i].type = REF;
				continue;
			}

			prev_type = tokens[i - 1].type;
			if(!(prev_type == ')' || prev_type == NUM || prev_type == REG))
				tokens[i].type = REF;
		}
	}

	return eval(0, nr_token - 1, success);
}

